package com.jiepu.homework.module5.exercise3;

/*
 * Stack代表一类可以按照“先进后出、后进先出”规则保存数据的容器
 * Stack的每一个对象就代表具体的一个容器
 * 
 * 分析过程：
 * 1、给出的测试类中调用了两个方法push()、pop()
 * 测试类中是创建了一个Stack对象，然后让对象调用push()和pop()
 * 那就说明每个对象调用这些方法应该得到不同的结果，它们是实例方法。
 * 强调对象之间的个性差异：每个Stack对象都是一个独立的容器
 * 可以创建很多个Stack对象，获得很多个容器。
 * 但是它们之间彼此没有任何关联和影响。
 * 各自都能按照规则保存各自的数据。
 * 
 * 2、现在要用一个数组来模拟堆栈，就要选择数组的两个方向
 * 哪个做栈顶哪个做栈底。
 * 大致认为把[0]位置作为栈底计算起来比较方便。
 * 
 * 3、必须考虑程序的健壮性：
 * （1）当栈中存满元素之后怎么办，还能否执行压栈操作？
 * （2）当栈中没有元素的时候，还能否执行弹栈操作？
 */
public class Stack {

	// 真正的数据就是保存在每个Stack的对象array数组中的
	// 但是这个数组不能对外开放，需要封装
	// 如果公开这个数组，我们就无法控制用户是否按照堆栈的规则来插入和取出数据
	// 所以我们需要将其可见性降到最低，并且提供对外的访问接口
	// 不是让用户直接操作这个数组，而是让用户调用我们自己的方法
	// 告诉我们要插入的数字是多少，具体这个数字如何向数组中插入
	// 规则要由我们自己来定
	// 规则：每次插入数据都必须在所有已插入数据的最后边进行插入
	// 每次取出数据都只能取最后插入的那一个数据
	private int[] array;

	// 记录当前数组中已经保存的元素个数，也代表下一个元素应该插入的位置
	// size既代表下一个压栈位置，size-1代表当前应该弹栈位置
	// size实际上就是堆栈中【栈顶】
	private int size;

	// 数组的默认容量
	public final static int DEFAULT_CAPACITY = 100;

	// 默认初始长度为100
	public Stack() {
		this(DEFAULT_CAPACITY);
	}

	// 如果用户已经预见到了要保存的数据量非常庞大
	// 可以直接传入一个数组的初始化容量，一步到位把数组创建出来
	// 避免很多不必要的扩容操作
	public Stack(int initialCapacity) {
		if (initialCapacity <= 0) {
			initialCapacity = DEFAULT_CAPACITY;
		}
		// 也可以用三目运算符代替上述判断
		// initialCapacity = initialCapacity <= 0 ?
		// DEFAULT_CAPACITY : initialCapacity;
		array = new int[initialCapacity];
	}

	// 压栈方法
	public void push(int n) {
		// 先判断当前堆栈是否存满，则自动扩容
		ensureCapacity();
		array[size++] = n;
	}

	// 确保数组容量够用
	private void ensureCapacity() {
		if (size >= array.length) {
			// 数组长度以2倍增长
			int[] newArr = new int[array.length * 2];
			// 将原数组元素全部复制到新数组
			System.arraycopy(array, 0, newArr, 0, array.length);
			// 将新数组引用赋值给原数组
			array = newArr;
		}
	}

	// 弹栈方法不需要参数，因为每次要弹出的元素位置已经固定
	// 必须是array[size-1]这个元素
	public int pop() {
		// 如果当前栈为空（size=0）
		// 给出一个错误提示，直接返回方法
		if (size <= 0) {
			System.out.println("堆栈为空，弹栈失败！");
			return -1;
		}
		// 把删掉的元素返回
		return array[--size];
	}

}
